import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
class Student{

}


//实现大根堆
class IntCmp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
public class Test {
    //找第k大的元素就是小根堆的堆的堆顶元素
    //找第k小就是大根堆的堆顶元素
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());

    }
    //topk问题：求数据集合中前k个最大或者最小的元素，一般情况下数据量都比较大
    //做法1：把数组排序   排序之后   去除前10个最大的。数据量非常大的时候，你无法在内存中排序   x
    //做法2：把所有数据放到优先级队列中，出队k次就ok了  数据量非常大的时候，你无法放到优先级队列中   x
    //以上两种做法还有不好的地方     就是效率可能不会很高！！！
    //我们建议的做法：前K个最大的数据，用前K个元素建小根堆K（堆顶是这K个元素里面的最小值了）
    // 建一个i下标遍历剩余数组，如果i下标的元素大于堆顶元素 那么说明堆顶元素一定不是前K个最大的元素之一
    // 把剩下的元素每次与堆顶元素比较，把堆顶出队，再把i下标的元素入队
    //时间复杂度 O(K)+O(N-K)*log2K
    public int[] smallestK1(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k <= 0){
            return ret;
        }
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(arr.length);
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }

        for (int i = 0; i < k; i++) {
           ret[i] = priorityQueue.poll();
        }
        return  ret;
    }
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k <= 0){
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            if(priorityQueue.peek() > arr[i]){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return  ret;
    }
    //找最大的k个数
    public static int[] maxestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k <= 0){
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(arr.length);
        //先放k个元素进小根堆
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        //遍历剩下的元素
        for (int i = k; i < arr.length; i++) {
            int top = priorityQueue.peek();
            if(arr[i] > top){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
         ret[i] = priorityQueue.poll();
        }
        return ret;
    }
    public static void main2(String[] args) {
            int[] array = {16,4,17,28,47,35,46,77};
        System.out.println(Arrays.toString(maxestK(array, 3)));
        //默认情况是小根堆
        //使用了堆这种数据结构
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(10);
        priorityQueue.offer(9);
        priorityQueue.offer(5);
        priorityQueue.offer(4);
        System.out.println(priorityQueue.poll());
        //不能存放无法比较大小的对象
//        PriorityQueue<Student> studentPriorityQueue = new PriorityQueue<>();
//        studentPriorityQueue.offer(new Student());
//        studentPriorityQueue.offer(new Student());//报错
//        priorityQueue.offer(null);//异常

    }
    public static void main1(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        testHeap.initHeap(array);
        testHeap.creatHeap();
        //插入80
        testHeap.offer(80);
        System.out.println();
    }
}
